Tight bounds and conjectures for the isolation lemma

摘要

Given a hypergraph $H$ and a weight function $w: V \rightarrow \{1, \dots,M\}$ on its vertices, we say that $w$ is isolating if there is exactly one edgeof minimum weight $w(e) = \sum_{i \in e} w(i)$. The Isolation Lemma is acombinatorial principle introduced in Mulmuley et. al (1987) which gives alower bound on the number of isolating weight functions. Mulmuley used this asthe basis of a parallel algorithm for finding perfect graph matchings. It has anumber of other applications to parallel algorithms and to reductions ofgeneral search problems to unique search problems (in which there are one orzero solutions). The original bound given by Mulmuley et al. was recently improved by Ta-Shma(2015). In this paper, we show improved lower bounds on the number of isolatingweight functions, and we conjecture that the extremal case is when $H$ consistsof $n$ singleton edges. When $M \gg n$ our improved bound matches this extremalcase asymptotically. We are able to show that this conjecture holds in a number of special cases:when $H$ is a linear hypergraph or is 1-degenerate, or when $M = 2$. We alsoshow that it holds asymptotically when $M \gg n \gg 1$.